package main;

import java.util.Collections;

/**
 * @author zhx
 * @since 2020-07-06
 * 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 * <p>
 *  
 * <p>
 * 示例1:
 * <p>
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode25 {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        int[][] dp = new int[n][n]; // dp[1][1]:表示长度为1的子数组选择第2个元素时的和

        // 填充长度的为1的子数组
        for (int i = 0; i < n; i++) {
            dp[i][0] = nums[i];
            max = Math.max(max,nums[i]);
        }
        // fill the first column of dp;
        for (int i = 1; i < n; i++){
            dp[0][i] = dp[0][i-1] + nums[i];
            max = Math.max(max,dp[0][i]);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < (n - i); j++) {
//                dp[i][j] = subArraySum(i,j,nums);
                dp[i][j] = dp[i-1][j] + nums[i+j] - nums[i-1];
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;
    }
    private int subArraySum(int i,int j,int[] arr){
        int sum = 0;
        for (;j >= 0;j--){
            sum += arr[i];
            i++;
        }
        return sum;
    }
}
